#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
int n,m;
int father[1010];
int next[1010];
int inf=(~(1<<31));
struct arc
{
	int link;
	int flow;
	int cost;
	int rp;
	arc(int l,int f,int co,int r)
	{
		link=l,flow=f,cost=co,rp=r;
	}
};
vector<arc> a[1010];
int SPFA(int vs,int vt)
{
	int w[1010],from,i,t;
	bool done[1010];
	queue<int> mq;
	fill(w,w+1010,inf);
	fill(done,done+1010,false);
	mq.push(vs);
	w[vs]=0;
	while(!mq.empty())
	{
		from=mq.front();
		mq.pop();
		done[from]=0;
		for(i=0;i<a[from].size();i++)
		{
			t=a[from][i].link;
			if(a[from][i].flow&&a[from][i].cost+w[from]<w[t])
			{
				w[t]=a[from][i].cost+w[from];
				father[t]=from;
				next[t]=i;
				if(!done[t])
				{
					mq.push(t);
					done[t]=1;
				}
			}
		}
	}
    return w[vt];
}
int f(int vs,int vt)
{
    int t,sum=0,i,n=2,j,link;
	//fill(father,father+1010,-1);
    while(n--)
    {
        t=SPFA(vs,vt);
        for(i=vt;i!=vs;i=father[i])
        {
            j=a[father[i]][next[i]].rp;
			a[father[i]][next[i]].flow--;
            a[i][j].flow++;
            a[i][j].cost=-a[father[i]][next[i]].cost;
        }
        sum+=t;
    }
    return sum;
}
void add(int v1,int v2,int flow,int cost)
{
    a[v1].push_back(arc(v2,flow,cost,a[v2].size()));
    a[v2].push_back(arc(v1,flow,cost,a[v1].size()-1));
}
int main()
{
	int from,to,i,j,cost;
    while(cin>>n>>m)
    {
		//for(i=0;i<1010;i++) a[i].clear();
		while(m--)
		{
			scanf("%d%d%d",&from,&to,&cost);
			add(from,to,1,cost);
		}
		//add(0,1,2,0),add(n,n+1,2,0);
		cout<<f(1,n)<<endl;
    }
	return 0;
}
